package com.hxm.demo.test1;

/**
 * description: add a description
 *
 * @author huangxiaoming
 * @version 1.0.0
 * @date 2022/10/09 14:30:30
 */
public class TestFindMedianSortedArrays {

    /**
     * 4. 寻找两个正序数组的中位数
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 2};
        int[] nums2 = new int[]{3, 4};
        System.out.println(findMedianSortedArrays(nums1, nums2));
    }

    /**
     * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
     * <p>
     * 算法的时间复杂度应该为 O(log (m+n)) 。
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m == 0 && n == 0) {
            return 0;
        }
        int[] result = new int[m + n];
        int i = 0, j = 0, k = 0;
        while (i < m || j < n) {
            if (i >= m && j < n) {
                result[k] = nums2[j];
                j++;
            }
            if (i < m && j >= n) {
                result[k] = nums1[i];
                i++;
            }
            if (i < m && j < n) {
                if (nums1[i] < nums2[j]) {
                    result[k] = nums1[i];
                    i++;
                } else {
                    result[k] = nums2[j];
                    j++;
                }
            }
            k++;
        }

        if ((m + n) % 2 == 1) {
            return result[(m + n + 1) / 2 - 1];
        } else {
            return (result[(m + n) / 2] + result[(m + n) / 2 - 1]) / 2.0;
        }
    }
}
